class Node(object):

    """A node in a doubly-linked list."""

    def __init__(self, value, prev=None, next=None):
        self.prev = prev
        self.value = value
        self.next = next


class Deque(object):

    """An implementation of a deque.

    __contains__ is not implemented as Python automatically uses the iterator
    of an object to perform a linear search.

    """

    def __init__(self):
        """Create an empty deque."""
        self._length = 0
        self._head = None
        self._tail = None

    def __iter__(self):
        """Iterate over all values in the deque."""
        current = self._head
        while current is not None:
            yield current.value
            current = current.next

    def __str__(self):
        """Represent deques like a list."""
        return '[' + ', '.join(map(str, self)) + ']'

    def __len__(self):
        return self._length

    def __getitem__(self, index):
        """Return the value at the specified index."""
        if index >= 0:
            node = self._head
            for count in xrange(index):
                node = node.next
        else:
            node = self._tail
            for count in xrange(abs(index)-1):
                node = node.prev
        return node.value

    def push_left(self, value):
        """Push on to the left/front/head of the deque."""
        node = Node(value)
        old_node = self._head
        self._head = node
        if old_node is None:
            self._tail = node
        else:
            self._head.next = old_node
            old_node.prev = self._head
        self._length += 1

    def push_right(self, value):
        """Push on to the right/end/tail of the deque."""
        node = Node(value)
        old_node = self._tail
        self._tail = node
        if old_node is None:
            self._head = node
        else:
            self._tail.prev = old_node
            old_node.next = self._tail
        self._length += 1

    def pop_left(self):
        """Remove the item from the left/front/head and return its value."""
        node = self._head
        self._head = self._head.next
        if self._head is None:
            self._tail = None
        else:
            self._head.prev = None
        self._length -= 1
        return node.value

    def pop_right(self):
        """Remove the item from the right/end/tail and return its value."""
        node = self._tail
        self._tail = self._tail.prev
        self._tail.next = None
        if self._tail is None:
            self._head = None
        else:
            self._tail.next = None
        self._length -= 1
        return node.value

    def peek_left(self):
        """Return the value at the left/front/head."""
        return self._head.value

    def peek_right(self):
        """Return the value at the right/end/tail."""
        return self._tail.value


def main(*tokens):
    """Perform the commands."""
    token_stream = iter(tokens)
    translate = {'length': '__len__', 'index': '__getitem__',
                    'repr': '__str__'}
    takes_arg = set(['push_left', 'push_right', '__getitem__', 'contains'])
    print_return = set(['pop_left', 'pop_right', 'peek_left', 'peek_right',
                        '__len__', '__getitem__', '__str__'])
    deque = Deque()
    try:
        while True:
            token = token_stream.next()
            args = []
            # Commands that do not directly map to their method name.
            if token in translate.keys():
                token = translate[token]
            # Get the arg, if needed.
            if token in takes_arg:
                args.append(int(token_stream.next()))
            # Special-casing.
            if token == 'contains':
                print str(args[0] in deque).lower()
            # General case.
            else:
                returned = getattr(deque, token)(*args)
                if token in print_return:
                    print returned
                else:
                    print deque
    except StopIteration:
        pass


if __name__ == '__main__':
    from sys import argv
    main(*argv[1:])
